package skewreduce.lib;

import java.io.BufferedInputStream;
import java.io.BufferedOutputStream;
import java.io.DataInput;
import java.io.DataInputStream;
import java.io.DataOutput;
import java.io.DataOutputStream;
import java.io.EOFException;
import java.io.File;
import java.io.FileInputStream;
import java.io.FileOutputStream;
import java.io.IOException;
import java.util.Arrays;

import org.apache.hadoop.io.Writable;


/**
 * new partitioning scheme
 */
public class Cube2 extends Partition {
    Point3D mp;
    Point3D Mp;
    Split   split;
    byte    skinMask;
    
    public static interface Split extends Writable {
    	public void set(String[] spec);
    	public boolean isLeft(ITuple t);
    	public int getArity();
    	
    	public int getMajorAxis();
    	public float getMajorSplit();
    	public void toSpec(StringBuilder buf);
    }
  
    
    static final class SingleAxisSplit implements Split {
    	int axis;
    	float split;
    	float leftProb;
    	
    	SingleAxisSplit() {}
    	
    	SingleAxisSplit(int a,float s) {
    		this(a,s,0.0f);
    	}
    	
		public SingleAxisSplit(int a, float s, float p) {
    		axis = a;
    		split = s;
    		leftProb = p;
		}

		@Override
		public boolean isLeft(ITuple t) {
			float v = t.getFloat(axis);
			if ( v < split ) return true;
			if ( v > split ) return false;
			return leftProb == 0.0f ? false : Math.random() < leftProb;
		}
		
		@Override
		public void set(String[] spec) {
		  axis = Integer.parseInt(spec[0]);
		  split = Float.parseFloat(spec[1]);
		  if ( spec.length > 2 ) {
		  	leftProb = Float.parseFloat(spec[2]);
		  }
		}
		
		@Override
		public void readFields(DataInput in) throws IOException {
			axis = in.readByte();
			split = in.readFloat();
			leftProb = in.readFloat();
		}
		@Override
		public void write(DataOutput out) throws IOException {
			out.writeByte(1);
			out.writeByte(axis);
			out.writeFloat(split);
			out.writeFloat(leftProb);
		}

		@Override
		public int getArity() {
			return 1;
		}

		@Override
		public int getMajorAxis() {
			return axis;
		}

		@Override
		public float getMajorSplit() {
			return split;
		}

		@Override
		public void toSpec(StringBuilder buf) {
			buf.append(1);
			buf.append(';');
			buf.append(axis);
			buf.append(';');
			buf.append(split);
			buf.append(';');
			buf.append(leftProb);
		}
		
		@Override
		public String toString() {
			StringBuilder b = new StringBuilder();
			toSpec(b);
			return b.toString();
		}
    }
    
    static final class MultipleAxesSplit implements Split {
    	int[]   axes;
    	float[] split;
    	float leftProb;
    	
    	MultipleAxesSplit(int n) {
    		axes = new int[n];
    		split = new float[n];
    	}

		public MultipleAxesSplit(int[] a, float[] sp, float prob) {
			axes = Arrays.copyOf(a, sp.length);
			split = sp.clone();
			leftProb = prob;
		}

		@Override
		public boolean isLeft(ITuple t) {
			for ( int i = 0; i < axes.length; ++i ) {
				float v = t.getFloat(axes[i]);
				if ( v < split[i] ) return true;
				if ( v > split[i] ) return false;
			}
			// same for all splitting axes
			return ( leftProb == 0.0f ) ? false : Math.random() < leftProb;
		}

		@Override
		public void set(String[] spec) {
			String[] a = spec[0].split(",");
			String[] s = spec[1].split(",");
			if ( a.length != axes.length || s.length != axes.length )
				throw new IllegalArgumentException("Not enough arguments to initialize split information");
			for ( int i = 0; i < axes.length; ++i ) {
				axes[i] = Integer.parseInt(a[i]);
				split[i] = Float.parseFloat(s[i]);
			}
			if ( spec.length > 2 ) {
				leftProb = Float.parseFloat(spec[2]);
			} else {
				leftProb = 0.0f;
			}
		}

		@Override
		public void readFields(DataInput in) throws IOException {
			for ( int i = 0; i < axes.length; ++i )
				axes[i] = in.readByte();
			for ( int i = 0; i < split.length; ++i )
				split[i] = in.readFloat();
			leftProb = in.readFloat();
		}

		@Override
		public void write(DataOutput out) throws IOException {
			out.writeByte(axes.length);
			for ( int axis : axes )
				out.writeByte(axis);
			for ( float s : split )
				out.writeFloat(s);
			out.writeFloat(leftProb);
		}

		@Override
		public int getArity() {
			return axes.length;
		}

		@Override
		public int getMajorAxis() {
			return axes[0];
		}

		@Override
		public float getMajorSplit() {
			return split[0];
		}

		@Override
		public void toSpec(StringBuilder buf) {
			buf.append(axes.length);
			buf.append(';');
			for ( int i = 0; i < axes.length; ++i ) {
				buf.append(axes[i]);
				buf.append(',');
			}
			buf.setLength(buf.length()-1);
			buf.append(';');

			for ( int i = 0; i < axes.length; ++i ) {
				buf.append(split[i]);
				buf.append(',');
			}
			buf.setLength(buf.length()-1);
			buf.append(';');
			
			buf.append(leftProb);
		}
		
		@Override
		public String toString() {
			StringBuilder b = new StringBuilder();
			toSpec(b);
			return b.toString();
		}
    }
    
    static Split createSplitInstance(byte n) {
    	if ( n == 0 ) {
    		return null;
    	} else if ( n == 1 ) {
    		return new SingleAxisSplit();
    	}
    	return new MultipleAxesSplit(n);
    }

    public Cube2() {}

    public Cube2(long d,float sz) {
        id = d;
        float half = sz * 0.5f;
        mp = new Point3D(-half,-half,-half);
        Mp = new Point3D(half,half,half);
        split = null;
        skinMask = 0x3f; // include all surfaces
    }

    public Cube2(String spec) {
    	super(spec);
    }

    public Cube2(long id,int lv,Point3D m,Point3D M,byte mask) {
    	super(id,lv);
        this.mp = m;
        this.Mp = M;
        this.skinMask = mask;
    }
    
    public Point3D getMinPoint() { return mp; }
    public Point3D getMaxPoint() { return Mp; }
    
    public float getSplit() { return split.getMajorSplit(); }
    public int getSplitAxis() { return split.getMajorAxis(); }
    /**
     * check whether splittingn axis are useless
     * @return
     */
    public boolean isSurfaceSplit() {
    	int axis = split.getMajorAxis();
    	float split = this.split.getMajorSplit();
    	return mp.getFloat(axis) == split || Mp.getFloat(axis) == split;
    }
    
    @Override
    public int getArity() { return 3; }

    @Override
    public double  getVolume() {
    	return (Mp.x - mp.x) * (Mp.y - mp.y) * (Mp.z - mp.z); 
    }
    
    @Override
    public Number getLength(int i) {
    	return Mp.getFloat(i) - mp.getFloat(i);
    }

    // split methods

    @Override
    public int uniformSplit(TerminalCondition cond) {
        int maxLv = getLevel();

        // eval split condition
        if ( cond.continueSplit(0,getLevel()) ) {
            Util.Axis axis2 = Util.Axis.get(getLevel());
            int axis = axis2.ordinal();
            float split = (axis2.get(mp) + axis2.get(Mp)) * 0.5f;

            float lMx = ( axis2 == Util.Axis.X ) ? split : Mp.getX();
            float lMy = ( axis2 == Util.Axis.Y ) ? split : Mp.getY();
            float lMz = ( axis2 == Util.Axis.Z ) ? split : Mp.getZ();

            float rmx = ( axis2 == Util.Axis.X ) ? split : mp.getX();
            float rmy = ( axis2 == Util.Axis.Y ) ? split : mp.getY();
            float rmz = ( axis2 == Util.Axis.Z ) ? split : mp.getZ();

            left = new Cube2( 
                (getID()<<1),
                getLevel()+1,
                mp,
                new Point3D(lMx,lMy,lMz),
                (byte)(skinMask | (1 << (axis+3) ))
            );

            right = new Cube2( 
                (getID()<<1)|0x01,
                getLevel()+1,
                new Point3D(rmx,rmy,rmz),
                Mp,
                (byte)(skinMask | (1 << (axis)))
            );

            maxLv = Math.max(
                    left.uniformSplit(cond),
                    right.uniformSplit(cond) 
            );
            
            this.split = new SingleAxisSplit(axis,split);
        }
        return maxLv;
    }
    
    public String toLongString() {
    	java.io.StringWriter wr = new java.io.StringWriter(8192);
    	java.io.PrintWriter out = new java.io.PrintWriter(wr);
    	print(out);
    	out.flush();
    	out.close();
    	return wr.getBuffer().toString();
    }

	@Override
	public <T extends ITuple> boolean atCore(T q, Number eps) {
    	IPoint3D p = (IPoint3D)q;
    	float r = eps.floatValue();
        return mp.getX()+r < p.getX() && p.getX() < Mp.getX()-r
                && mp.getY()+r < p.getY() && p.getY() < Mp.getY()-r
                && mp.getZ()+r < p.getZ() && p.getZ() < Mp.getZ()-r;
	}

	@Override
	public final <T extends ITuple> boolean atSkin(T q, Number eps) {
		if ( skinMask == 0x00 )
			// none needs to be included
			return false;
		
		boolean result = super.atSkin(q,eps);
		if ( skinMask >= 0x3f || ! result ) {
			return result;
		}
		
    	IPoint3D p = (IPoint3D)q;
    	float r = eps.floatValue();
    	
    	// filter out unnecessary surfaces
    	
    	// 000 001 : L x-axis
    	// 000 010 : L y-axis
    	// 000 100 : L z-axis
    	// 001 000 : R x-axis
    	// 010 000 : R y-axis
    	// 100 000 : R z-axis

    	if ( (skinMask & 0x01) > 0 && p.getX() <= mp.getX()+r ) return true;
    	if ( (skinMask & 0x02) > 0 && p.getY() <= mp.getY()+r ) return true;
    	if ( (skinMask & 0x04) > 0 && p.getZ() <= mp.getZ()+r ) return true;
    	if ( (skinMask & 0x08) > 0 && p.getX() >= Mp.getX()-r ) return true;
    	if ( (skinMask & 0x10) > 0 && p.getY() >= Mp.getY()-r ) return true;
    	if ( (skinMask & 0x20) > 0 && p.getZ() >= Mp.getZ()-r ) return true;
    	
    	return false;
	}
	
	public <T extends ITuple> boolean atMergeSurface(T q,Number eps) {
		float v = q.getFloat(split.getMajorAxis());
		float r = eps.floatValue();
		float sv = split.getMajorSplit();
		return sv - r <= v && v <= sv + r;
	}

	@Override
	public <T extends ITuple> boolean contains(T q) {
    	IPoint3D p = (IPoint3D)q;
    	return mp.getX() <= p.getX() && p.getX() <= Mp.getX()
                && mp.getY() <= p.getY() && p.getY() <= Mp.getY()
                && mp.getZ() <= p.getZ() && p.getZ() <= Mp.getZ();
	}

	@Override
	protected Partition newInstance() {
		return new Cube2();
	}

	@Override
	public void readInternalFields(DataInput in) throws IOException {
        mp = Point3D.read(in);
        Mp = Point3D.read(in);
        byte n = in.readByte();
        split = Cube2.createSplitInstance(n);
        if ( split != null ) {
        	split.readFields(in);
        }
//        axis = in.readInt();
//        split = in.readFloat();
//        leftProb = in.readFloat();
        skinMask = in.readByte();
	}

	@Override
	protected void setInternal(String[] fld) {
        if ( fld == null || fld.length < 2 )
            throw new IllegalArgumentException();

        mp = new Point3D(fld[0]);
        Mp = new Point3D(fld[1]);
        if ( fld.length > 2 ) {
        	skinMask = Byte.parseByte(fld[2]);
        }
        if ( fld.length > 4) {
        	byte n = Byte.parseByte(fld[3]);
        	split = Cube2.createSplitInstance(n);
        	if ( split != null ) {
        		split.set(Arrays.copyOfRange(fld, 4, fld.length));
        	}
//            axis = Integer.parseInt(fld[3]);
//            split = Float.parseFloat(fld[4]);
//            if ( fld.length > 5 ) {
//            	leftProb = Float.parseFloat(fld[5]);
//            }
        } else {
        	split = null;
        }
	}

	@Override
	protected void setInternal(Partition org) {
		Cube2 cube = (Cube2)org;
		mp = cube.mp;
		Mp = cube.Mp;
		skinMask = cube.skinMask;
		
		split = cube.split; // TODO make it cloneable!
//		axis = cube.axis;
//		split = cube.split;
//		leftProb = cube.leftProb;
	}

	@Override
	protected void toSpecInternal(StringBuilder buf) {
        buf.append(mp);
        buf.append(';');
        buf.append(Mp);
        buf.append(';');
        buf.append(skinMask);
        buf.append(';');
        
        if ( split == null ) {
        	buf.append('0');
        } else {
        	split.toSpec(buf);
        }
	}

	@Override
	protected String toStringInternal() {
		return String.format("%s;%s;%02x;%s;%f",mp,Mp,skinMask,( split == null ) ? "0" : split ,getVolume());
	}

	@Override
	public <T extends ITuple> int split(T[] arr, int from, int to,
			skewreduce.lib.Partition.TerminalCondition cond) {
        int maxLv = getLevel();
        if ( from < to ) {
            int len = to - from + 1;
            int med = len >> 1;

            // eval split condition
            if ( cond.continueSplit(len,getLevel()) ) {
                Util.Axis axis2 = Util.Axis.get(getLevel());
                int axis = axis2.ordinal();
                Util.findKMedian(arr, med+1, from, to, axis2);

                float split = axis2.get(arr[from+med]);

                float lMx = ( axis2 == Util.Axis.X ) ? split : Mp.getX();
                float lMy = ( axis2 == Util.Axis.Y ) ? split : Mp.getY();
                float lMz = ( axis2 == Util.Axis.Z ) ? split : Mp.getZ();

                float rmx = ( axis2 == Util.Axis.X ) ? split : mp.getX();
                float rmy = ( axis2 == Util.Axis.Y ) ? split : mp.getY();
                float rmz = ( axis2 == Util.Axis.Z ) ? split : mp.getZ();

                left = new Cube2( 
                    (getID()<<1),
                    getLevel()+1,
                    mp,
                    new Point3D(lMx,lMy,lMz),
                    (byte)(skinMask | (1 << (axis+3) ))
                );

                right = new Cube2( 
                    (getID()<<1)|0x01,
                    getLevel()+1,
                    new Point3D(rmx,rmy,rmz),
                    Mp,
                    (byte)(skinMask | (1 << axis))
                );

                maxLv = Math.max(
                        left.split(arr,from,from+med-1,cond),
                        right.split(arr,from+med+1,to,cond) );
                
                this.split = new SingleAxisSplit(axis,split);
            }
        }
        return maxLv;
    }

	@Override
	protected <T extends ITuple> Partition whichPartition(T x) {
//		float v = x.getFloat(axis);
//		if ( v == split && leftProb > 0.0f ) {
//			return ( Math.random() < leftProb ) ? left : right;
//		}
//        return ( v < split ) ? left : right;
		boolean l = split.isLeft(x);
		return ( l ) ? left : right;
	}

	@Override
	public void writeInternalFields(DataOutput out) throws IOException {
        mp.write(out);
        Mp.write(out);
//        out.writeInt(axis);
//        out.writeFloat(split);
//        out.writeFloat(leftProb);
        if ( split == null ) {
        	out.writeByte(0);
        } else {
        	split.write(out);
        }
        out.write(skinMask);
	}

	public void setSplit(int axis,float sp) {
		setSplit(axis,sp,0.5f);
	}

	public void setSplit(int a,float sp,float prob) {
		int axis = a;
		float split = sp;
		float leftProb = prob;
		
		float lMx = ( axis == 0 ) ? split : Mp.getX();
        float lMy = ( axis == 1 ) ? split : Mp.getY();
        float lMz = ( axis == 2 ) ? split : Mp.getZ();

        float rmx = ( axis == 0 ) ? split : mp.getX();
        float rmy = ( axis == 1 ) ? split : mp.getY();
        float rmz = ( axis == 2 ) ? split : mp.getZ();

        left = new Cube2( 
                (getID()<<1),
                getLevel()+1,
                getMinPoint(),
                new Point3D(lMx,lMy,lMz),
	            (byte)(skinMask | (1 << (axis+3)))
        );

        right = new Cube2( 
	            (getID()<<1)|0x01,
	            getLevel()+1,
	            new Point3D(rmx,rmy,rmz),
	            getMaxPoint(),
                (byte)(skinMask | (1 << axis ))
        );
        
        this.split = new SingleAxisSplit(axis,split,leftProb);
	}

	public void setSplit(int[] a,float[] sp,float prob) {
		float sv = sp[0];
		int axis = a[0];
		
		float lMx = ( axis == 0 ) ? sv : Mp.getX();
        float lMy = ( axis == 1 ) ? sv : Mp.getY();
        float lMz = ( axis == 2 ) ? sv : Mp.getZ();

        float rmx = ( axis == 0 ) ? sv : mp.getX();
        float rmy = ( axis == 1 ) ? sv : mp.getY();
        float rmz = ( axis == 2 ) ? sv : mp.getZ();

        left = new Cube2( 
                (getID()<<1),
                getLevel()+1,
                getMinPoint(),
                new Point3D(lMx,lMy,lMz),
	            (byte)(skinMask | (1 << (axis+3)))
        );

        right = new Cube2( 
	            (getID()<<1)|0x01,
	            getLevel()+1,
	            new Point3D(rmx,rmy,rmz),
	            getMaxPoint(),
                (byte)(skinMask | (1 << axis ))
        );
        
        this.split = new MultipleAxesSplit(a,sp,prob);
	}

	@Override
	public Partition[] split(int axis, Number v, float lprob) {
		setSplit(axis,v.floatValue(),lprob);
		return new Partition[] { left, right };
	}
	
	@Override
	public Partition getMergingArea(Partition l,Partition r,Number eps) {
		Cube2 lc = (Cube2)l;
		Cube2 rc = (Cube2)r;
		float R = eps.floatValue();
		
		Point3D lMp = lc.getMaxPoint();
		Point3D rmp = rc.getMinPoint();
		
		int splitAxis;
		for ( splitAxis = 0; lMp.getFloat(splitAxis) != rmp.getFloat(splitAxis); ++splitAxis );
		
		// we got split axis. copy values
		float mx = ( splitAxis == 0 ) ? rmp.getX() - R : rmp.getX();
		float my = ( splitAxis == 1 ) ? rmp.getY() - R : rmp.getY();
		float mz = ( splitAxis == 2 ) ? rmp.getZ() - R : rmp.getZ();
		
		float Mx = ( splitAxis == 0 ) ? lMp.getX() + R : lMp.getX();
		float My = ( splitAxis == 1 ) ? lMp.getY() + R : lMp.getY();
		float Mz = ( splitAxis == 2 ) ? lMp.getZ() + R : lMp.getZ();
		
		return new Cube2(-1,-1,new Point3D(mx,my,mz),new Point3D(Mx,My,Mz),(byte)0);
	}

	@Override
	public Partition[] split(int[] axis, float[] v, float lprob) {
		if ( v.length == 1 ) {
			setSplit(axis[0],v[0],lprob);
		} else {
			setSplit(axis,v,lprob);
		}
		return new Partition[] { left, right };
	}
	
	public static void main(String[] args) throws Exception {
		String outFileName = null;
		int depth = 0;
		String spec = null;
		String pfName = null;
		
		int i;
		for ( i = 0; i < args.length; ++i ) {
			if ( args[i].charAt(0) != '-' ) break;
			
			if ( "-out".equals(args[i]) ) {
				outFileName = args[++i];
			} else if ( "-depth".equals(args[i]) ) {
				depth = Integer.parseInt(args[++i]);
			} else if ( "-pf".equals(args[i]) ) {
				pfName = args[++i];
			} else if ( "-numPart".equals(args[i]) ) {
				int n = Integer.parseInt(args[++i]);
				depth = 0;
				while ( n > 1 ) {
					n >>>= 1;
					++depth;
				}
			} else if ( "-spec".equals(args[i]) ) {
				spec = args[++i];
			} else {
				throw new IllegalArgumentException("Unknown option: "+args[i]);
			}
		}
		
		if ( pfName == null ) {
			File f = new File(args[i]);
			int numRecs = (int)(f.length() / 20);
			Point3D[] nodes = new Point3D[numRecs];
			FileInputStream fis = new FileInputStream(f);
			DataInputStream input = new DataInputStream(new BufferedInputStream(fis,8192*1024));
			int n = 0;
			try {
				while ( true ) {
					input.readLong();
					Point3D p = new Point3D();
					p.readFields(input);
					nodes[n++] = p;
				}
			} catch ( EOFException x ) {
			} finally {
				fis.close();
			}
			
			Cube2 root = ( spec == null ) ? new Cube2(0,1.0f) : new Cube2(spec);
			Partition.build(root, nodes, n, new Cube2.DepthCondition(root,depth));
			
			if ( outFileName == null ) {
				root.print(System.out);
			} else {
				DataOutputStream out = new DataOutputStream(new BufferedOutputStream(new FileOutputStream(outFileName),8192*1024));
				root.write(out);
				out.close();
			}
		} else {
			Cube2 root = new Cube2();
			DataInputStream din = new DataInputStream(new FileInputStream(pfName));
			root.readFields(din);
			din.close();
			
			// query
			root.lookup(new Partition.ID("9-18"));
			root.lookup(new Partition.ID("10-52"));
		}
	}
}